/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package euclidesalgorithm;

/**
 *
 * @author atila
 */
public class EuclidesAlgorithm {

   public static final long MOD_RSA = 1L;

   /**
    * Maximo Divisor Comum (MDC). Great Commom Divisor(GCD)
    * @param e
    * @param z
    * @return
    */
   public long gcd(long e, long z) {
      long great = 0L;
      long aux = 0L;
      if (e > z) {
         while (e % z != 0) {
            aux = e % z;
            e = z;
            z = aux;
         }
         great = z;
      } else {
         while (z % e != 0) {
            aux = z % e;
            z = e;
            e = aux;
         }
         great = e;
      }
      return great;
   }

   /**
    * Encontra o valor de "e", o qual possui a propriedade 0 < e < (p * q) com mdc(e,z) = 1
    * @param z
    * @param p
    * @param q
    * @return
    */
   public long findE(long z, long p, long q) {
      long great = 0;
      long e = 2; // suposição.
      while (great != 1) {
         e = e + 1;
         great = gcd(e, z);
         z = (p - 1) * (q - 1);
      }
      return e;
   }

   public long module(long numA, long numB) {
      /*long mod = numA % numB;
      if ((mod < 0) && (numB > 0)) {
      return (numB + mod);
      } else if ((mod > 0) && (numB < 0)) {
      return (numB + mod);
      } else {
      return 0L;
      }*/
      if (numA < 0) {
         numA = -numA;
      }

      if (numB < 0) {
         numB = -numB;
      }

      if (numB == 0) {
         return numA;
      } else {
         return module(numB, numA % numB);
      }
   }

   public long extendAlgorithm(long e, long z) {
      long u1 = 1, u2 = 0, u3 = z;
      long v1 = 0, v2 = 1, v3 = e;

      while (v3 != 0) {
         long q = (long) Math.floor(u3/v3);
         long t1 = u1 - q * v1;
         long t2 = u2 - q * v2;
         long t3 = u3 - q * v3;

         u1 = v1;
         u2 = v2;
         u3 = v3;

         v1 = t1;
         v2 = t2;
         v3 = t3;
      }
      
      if (u2 < 0) {
         return u2 + z;
      } else {
         return u2;
      }
   }

   public String encript(String message) {
      return null;
   }

   public String decript(String encriptedMessage) {
      return null;
   }
}
